import java.util.HashMap;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2021/12/7
 * \* Time: 15:46
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */

class ListNode{
    public int val;
    public ListNode next;

    public ListNode(int val){
        this.val=val;
    }
}
public class MyLinkedList<RandomListNode> {
    public ListNode head;
    public void creatList(){
        ListNode listNode1=new ListNode(11);
        ListNode listNode2=new ListNode(11);
        ListNode listNode3=new ListNode(11);
        ListNode listNode4=new ListNode(11);
        ListNode listNode5=new ListNode(11);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
    }

    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head;
        ListNode curNext = head.next;
        cur.next = null;
        cur = curNext;
        while (cur != null) {
            curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
    public ListNode removeElements(ListNode head, int val){
        if(head==null)return head;
        ListNode cur=this.head;
        ListNode del=cur.next;
        while (cur!=null){
            if(del.val==val){
                cur.next=del.next;
                del=del.next;
            }else {
                cur=del;
                del=del.next;
            }
        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }

    public ListNode deleteNode (ListNode head, int val) {
        // write code here

        while (head!=null){
            if (head.val==val){
                return head.next;
            }else {
                ListNode cur=this.head;
                cur=cur.next;
                if(cur.val==val){
                    cur=cur.next;
                }
            }
        }
        return head;
    }

    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if (k<0)return null;
        ListNode fast=pHead;
        ListNode slow=pHead;
        while (k>0){
            fast=fast.next;
            k--;
        }

        while (fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast=pHead;
        ListNode slow=pHead;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        return slow;
    }

    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newHead=new ListNode(-1);
        ListNode tmp=newHead;

       while (list1!=null&&list2!=null){
           if (list1.val>list2.val){
               tmp.next=list2;
               tmp=list2;
               list2=list2.next;
           }
           if (list1.val<list2.val){
               tmp.next=list1;
               tmp=list1;
               list1=list1.next;
           }
       }

        return newHead.next;

    }


}
